// leetcode.algorithms.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <stack>
#include <queue>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>

using namespace std;

struct ListNode {
  int val;
  ListNode* next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class list_solution
{
public:

  ListNode* sortList(ListNode* head) {
  }

  ListNode* reverse(ListNode* head) {
    ListNode* pre = nullptr, * cur = head;
    while (cur != nullptr)
    {
      ListNode* next = cur->next;
      cur->next = pre;
      pre = cur;
      cur = next;
    }
    return pre;
  }

  bool isPalindrome(ListNode* head) {
    ListNode* slow = head, * fast = head;
    while (fast != nullptr && fast->next != nullptr) {
      slow = slow->next;
      fast = fast->next->next;
    }
    if (fast != nullptr) {
      slow = slow->next;
    }
    slow = reverse(slow);
    fast = head;
    while (slow != nullptr)
    {
      if (slow->val != fast->val)
        return false;
      slow = slow->next;
      fast = fast->next;
    }
    return true;
  }

  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (l1 == nullptr) return l2;
    if (l2 == nullptr) return l1;
    ListNode dummy(-1);
    ListNode* p = &dummy;
    while (l1 != nullptr && l2 != nullptr)
    {
      if (l1->val >= l2->val)
      {
        p->next = l2;
        l2 = l2->next;
      }
      else
      {
        p->next = l1;
        l1 = l1->next;
      }
      p = p->next;
    }
    p->next = l1 == nullptr ? l2 : l1;
    return dummy.next;
  }

  ListNode* reverseListWithStack(ListNode* head) {
    ListNode* newHead = head;
    stack<int> s;

    do {
      s.push(newHead->val);
      newHead = newHead->next;
    } while (newHead);

    if (s.empty())
      return nullptr;

    newHead = new ListNode(s.top(), nullptr);;
    ListNode* dummy = new ListNode();
    newHead->next = dummy;
    while (!s.empty()) {
      dummy = new ListNode(s.top(), nullptr);
      dummy = dummy->next;
      s.pop();
    }

    return newHead;
  }

  ListNode* reverseListWithoutStack(ListNode* head) {
    ListNode* newHead = nullptr;
    while (head != nullptr) {
      ListNode* temp = head->next;
      head->next = newHead;
      newHead = head;
      head = temp;
    }

    return newHead;
  }

  int length(ListNode* head) {
    int n = 0;
    while (head)
    {
      n++;
      head = head->next;
    }
    return n;
  }

  ListNode* removeNthFromEnd(ListNode* head, int n) {
    int len = length(head);
    int last = len - n;
    ListNode* prev = head;
    if (last == 0)
      return head->next;
    while (last--)
      prev = prev->next;
    prev->next = prev->next->next;
    return head;
  }

  ListNode* mergeTwoLists1(ListNode* l1, ListNode* l2) {
    ListNode* newHead = new ListNode();
    ListNode* curr = newHead;

    while (l1 != nullptr && l2 != nullptr)
    {
      if (l1->val >= l2->val)
      {
        curr->next = l2;
        l2 = l2->next;
      }
      else {
        curr->next = l1;
        l1 = l1->next;
      }
      curr = curr->next;
    }
    curr->next = l1 == nullptr ? l2 : l1;

    return newHead->next;
  }

  bool hasCycle(ListNode* head) {
    if (head == nullptr) return false;
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast != nullptr && fast->next != nullptr)
    {
      slow = slow->next;
      fast = fast->next->next;
      if (fast == slow)
        return true;
    }
    return false;
  }
};